package com.le.tester.imooc.oldfairy.coding.sorting;

import com.google.common.collect.Lists;
import org.junit.Test;

import java.util.List;
import java.util.stream.Collectors;

/**
 * createTime：2023/5/24 9:28
 * description：第一种快速排序
 */
public class QuickSort implements IImutableSorter {
    @Override
    public List<Integer> sort(List<Integer> list) {
        return this.quickSort(list);
    }

    //快速排序
    private List<Integer> quickSort(List<Integer> list) {
        if (list.size() <= 1) {
            return list;
        }

        //使用第一个为媒介
        Integer firstVal = list.get(0);

        //left
        List<Integer> left = list.stream().filter(item -> item < firstVal).collect(Collectors.toList());
        //mid
        List<Integer> mid = list.stream().filter(item -> item.equals(firstVal)).collect(Collectors.toList());
        //right
        List<Integer> right = list.stream().filter(item -> item > firstVal).collect(Collectors.toList());

        left = quickSort(left);
        right = quickSort(right);

        left.addAll(mid);
        left.addAll(right);

        return left;
    }

    @Test
    public void testQuickSort() {
        this.quickSort(Lists.newArrayList(1, 2, 7, 56, 89, 5, 12, 2, 5, 6, 9));
    }
}
